﻿#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef struct QueueNode
{
	int val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	struct QueueNode* phead;
	struct QueueNode* ptail;
	int size;
}Queue;

//初始化队列
void QueueInit(Queue* pq)
{
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
// ⼊队列，队尾
void QueuePush(Queue* pq, int x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		exit(-1);
		printf("malloc fail!\n");
	}
	newnode->val = x;
	newnode->next = NULL;

	if (pq->phead = NULL)
	{
		pq->phead = newnode;
		pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
// 出队列，队头
void QueuePop(Queue* pq)
{
	if (pq->size == 0)
	{
		printf("empty queue!");
		return;
	}

	QNode* temp = pq->phead;
	pq->phead = pq->phead->next;
	free(temp);

	pq->size--;
}
//取队头数据
int QueueFront(Queue* pq)
{
	if (pq->size == 0)
	{
		printf("empty queue!");
		return;
	}
	return pq->phead->val;
}
//取队尾数据
int QueueBack(Queue* pq)
{
	if (pq->size == 0)
	{
		printf("empty queue!");
		return;
	}
	return pq->ptail->val;
}
//队列判空
bool QueueEmpty(Queue* pq)
{
	if (pq->size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
//队列有效元素个数
int QueueSize(Queue* pq)
{
	return pq->size;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
	if (pq->size == 0)
	{
		printf("empty queue!");
		return;
	}

	QNode* pcur = pq->phead;
	while (pcur != NULL)
	{
		QNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}

	pq->phead = NULL;
	pq->ptail = NULL;
}


void Swap(int* x, int* y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

typedef struct Heap
{
	int* arr;
	int size;
	int capacity;
}HP;

//默认初始化堆
void HPInit(HP* php)
{
	php->arr = (int*)malloc(sizeof(int) * 4);
	if (php->arr == NULL)
	{
		printf("malloc fail!\n");
		exit(-1);
	}
	php->size = 0;
	php->capacity = 4;
}

void Dilatation(HP* php)
{
	int* temp = (int*)realloc(php->arr, php->capacity * 2 * sizeof(int));
	if (temp == NULL)
	{
		exit(-1);
	}
	php->arr = temp;
	php->capacity = php->capacity * 2;
}
//堆的插⼊
void HPPush(HP* php, int x)
{
	if (php->capacity == php->size)
	{
		Dilatation(php);
	}

	php->arr[php->size] = x;
	AdjustUp(php->arr, php->size);
	php->size++;
}
//堆的删除
int HPPop(HP* php)
{
	if (php->size == 0)
	{
		printf("empty heap!\n");
		return;
	}

	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	AdjustDown(php->arr, php->size - 1, 0);
}
//判空
bool HPEmpty(HP* php);
//求size
int HPSize(HP* php);
//堆的销毁
void HPDestroy(HP* php)
{
	free(php->arr);
	php->capacity = 0;
	php->size = 0;
}

//向上调整算法
void AdjustUp(int* arr, int child)
{
	int parent = (child + 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child + 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//向下调整算法
void AdjustDown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}

		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//利⽤给定数组初始化堆
void HPInitArray(HP* php, int* arr, int n)
{
	for (int i = (n - 1 - 1) / 2; i--; i >= 0)
	{
		AdjustDown(arr, n, i);
	}

	php->arr = arr;
	php->capacity = n;
	php->size = n;
}